package com.le.medium.class1;

import org.junit.Test;

import java.util.Arrays;

/**
 * 给定一个有序数组arr，代表数轴上从左到右有n个点arr[0]、arr[1]...arr[n－1]，
 * 给定一个正数L，代表一根长度为L的绳子，求绳子最多能覆盖其中的几个点
 */
public class Problem01_CordCoverMaxPoint {

    /**
     * 思路: 以每一个点作为绳子有边界判断最多能覆盖多少个点,寻找最左边界采用二分
     * 时间复杂度 O(n * log n)
     *
     * @param arr
     * @param L
     * @return
     */
    public static int maxPoint(int[] arr, int L) {
        if (arr == null || arr.length == 0 || L < 0) {
            return 0;
        }
        int res = 1;
        for (int i = 0; i < arr.length; i++) {
            int nearest = nearestIndex(arr, i, arr[i] - L);
            res = Math.max(res, i - nearest + 1);
        }
        return res;
    }

    /**
     * 寻找最左边界
     *
     * @param arr
     * @param R
     * @param val
     * @return
     */
    public static int nearestIndex(int[] arr, int R, int val) {
        int L = 0;
        int index = R;
        while (L <= R) {
            int mid = L + ((R - L) >> 1);
            if (arr[mid] >= val) {
                index = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return index;
    }

    /**
     * 思路二: 维持一个大小为绳子长度的窗口,以绳子左边界为起点,依次向右扩
     * @param arr
     * @param len
     * @return
     */
    public static int process(int[] arr, int len) {
        if (arr == null || arr.length == 0 || len < 0) {
            return 0;
        }
        int res = 0;
        int left = 0;
        int right = 0;
        while (left < arr.length && right < arr.length) {
            while (right < arr.length && arr[right] - arr[left] <= len) {
                res = Math.max(res, right - left + 1);
                right = right + 1;
            }
            left = left + 1;
        }
        return res;
    }

    public static int[] generateArray(int n){
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = (int) (Math.random() * 100) + 1;
        }
        Arrays.sort(res);
        return res;
    }

    @Test
    public void test() {
        System.out.println("hi");
        for (int i = 0; i < 1000000; i++) {
            int[] arr = generateArray(10);
            int L = arr[(int)Math.random()*10];
            if (maxPoint(arr,L) != process(arr,L)){
                System.out.println(Arrays.toString(arr));
                System.out.println(maxPoint(arr,L));
                System.out.println(process(arr,L));
                System.out.println("no");
                break;
            }
        }
    }

}
